package com.hy.treeNode3;

import com.hy.treeNode.TreeNode;

public class BuildTree {


    /**
     * 105.从前序与中序遍历序列构造二叉树
     *
     * 说到一层一层切割，就应该想到了递归。
     *
     * 来看一下一共分几步：
     *
     * 第一步：如果数组大小为零的话，说明是空节点了。
     *
     * 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
     *
     * 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
     *
     * 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
     *
     * 第五步：切割后序数组，切成后序左数组和后序右数组
     *
     * 第六步：递归处理左区间和右区间
     * @return
     */

    // 106.从中序与后序遍历序列构造二叉树
    public TreeNode buildTreeNode2(){
        // 中序遍历
        int [] inorder = {1,4,2,5,6,7,8};
        // 后置遍历
        int [] postorder = {1,2,4,6,8,7,5};
        return helper2(inorder,0,inorder.length,postorder,0,postorder.length);
    }

    public TreeNode helper2(int[] inorder,int inLeft,int inRight,int[] postorder,int postLeft,int postRight){
        // 没有元素
        // 没有元素了
        if (inRight - inLeft < 1) {
            return null;
        }
        // 只有一个元素了
        if (inRight - inLeft == 1) {
            return new TreeNode(inorder[inLeft]);
        }
        // 后序数组postorder里最后一个即为根结点
        int val = postorder[postRight - 1];
        TreeNode root = new TreeNode(val);
        int rootIndex = 0;
        // 根据根结点的值找到该值在中序数组inorder里的位置
        for (int i = inLeft; i < inRight; i++) {
            if (inorder[i] == val){
                rootIndex = i;
                break;
            }
        }
        // 根据rootIndex划分左右子树
        root.left = helper2(inorder, inLeft, rootIndex,
                postorder, postLeft, postLeft + (rootIndex - inLeft));
        root.right = helper2(inorder, rootIndex + 1, inRight,
                postorder, postLeft + (rootIndex - inLeft), postRight - 1);
        return root;
    }

    // 105.从前序与中序遍历序列构造二叉树
    public TreeNode buildTreeNode(){
        // 前序遍历
        int [] preorder = {5,4,1,2,7,6,8};
        // 中序遍历
        int [] inorder = {1,4,2,5,6,7,8};
        return helper(preorder,0,preorder.length -1,inorder,0,inorder.length -1);
    }

    public TreeNode helper(int[] preorder,int preLeft,int preRight,int[] inorder,int inLeft,int inRight){
        // 递归终止条件
        if (preLeft > preRight || inLeft > inRight){
            return null;
        }
        // val 为前序遍历第一个的值，也即是根节点的值
        // idx 为根据根节点的值来找中序遍历的下标
        int idx = inLeft,val = preorder[preLeft];
        TreeNode root = new TreeNode(val);
        for (int i = inLeft; i <= inRight; i++) {
            if (inorder[i] == val){
                idx = i;
                break;
            }
        }
        // 根据 idx 来递归找左右子树
        root.left = helper(preorder, preLeft + 1, preLeft + (idx - inLeft),
                inorder, inLeft, idx - 1);
        root.right = helper(preorder, preLeft + (idx - inLeft) + 1, preRight,
                inorder, idx + 1, inRight);
        return root;
    }

    public static void main(String[] args) {
        BuildTree buildTree = new BuildTree();

        System.out.println("106.从中序与后序遍历序列构造二叉树 : "+buildTree.buildTreeNode2().toString());
        System.out.println("105.从前序与中序遍历序列构造二叉树 : "+buildTree.buildTreeNode().toString());
    }
}
